/*
 * @Author: scl
 * @Date: 2023-08-27 14:48:54
 * @LastEditTime: 2023-08-27 14:55:55
 * @Description: file content
 */
/*
 * @lc app=leetcode.cn id=46 lang=typescript
 *
 * [46] 全排列
 *
 * https://leetcode.cn/problems/permutations/description/
 *
 * algorithms
 * Medium (78.89%)
 * Likes:    2660
 * Dislikes: 0
 * Total Accepted:    914.9K
 * Total Submissions: 1.2M
 * Testcase Example:  '[1,2,3]'
 *
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * 
 * 
 * 示例 3：
 * 
 * 
 * 输入：nums = [1]
 * 输出：[[1]]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= nums.length <= 6
 * -10 <= nums[i] <= 10
 * nums 中的所有整数 互不相同
 * 
 * 
 */

// @lc code=start
function permute(nums: number[]): number[][] {
    const len=nums.length,res=[],arr=[],used=new Array(len).fill(false)
    dfs(0)
    function dfs(depth){
        if(depth==len){
            res.push([...arr]);
            return
        }
        for(let i=0;i<len;i++){
            if(used[i])continue
            arr.push(nums[i])
            used[i]=true
            dfs(depth+1)
            arr.pop()
            used[i]=false
        }
    }
    return res
};
// @lc code=end

